https://leetcode-cn.com/problems/implement-strstr/submissions/

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        ret = -1
        needleLen = len(needle)
        if needleLen > len(haystack):
            return ret
        preList = self.preTable(needle)
        # print(haystack)
        # print(needle)
        # print(preList)
        ni = 0
        hi = 0
        hiMax = len(haystack) - needleLen + 1
        #遍历haystack
        #for hi in range(len(haystack) - needleLen + 1):
        while hi < hiMax:
            # print('hi',hi,'ni',ni)
            flag = True
            for o in range(ni, needleLen):
                # time.sleep(1)
                # print('[hi + o]=',hi + o,'[o]=',o)
                # print('haystack[hi + o]=',haystack[hi + o],'needle[o]=',needle[o])
                if haystack[hi + o] != needle[o]:
                    # print('notmatch')
                    flag = False
                    ni = preList[o]
                    if ni == 0:
                        hi += 1
                    else:
                        hi = hi + o - ni
                    break
            if flag:
                ret = hi
                break
        
        return ret
    
    def preTable(self, needle: str):
        ret = [0,0]
        # ret2 = [0,0]
        for head in [needle[:i+1] for i in range(1,len(needle)-1)]:
            #循环求前缀最大相同子串
            flag = False
            for i in range(1,len(head))[::-1]:
                if head[:i] == head[-i:]:
                    #相同
                    ret.append(i)
                    # ret2.append(len(head) - i)
                    flag = True
                    break
            if not flag:
                ret.append(0)
                # ret2.append(0)
                
        return ret#,ret2